1. Field of the Invention
The present invention generally relates to methods for routing in a network in a transport network, a routing system, and a transport system.
2. Description of the Related Art
Networks including nodes that are connected by links or edges may represent stops or stations for public transport means, which serve the stops in terms of bus lines, for example. Usually, shortest paths are calculated and presented to a user of the system in order to proceed from a start node to destination node in a time-efficient manner.
In the past, an optimal path between such start and destination nodes was calculated based on finding a minimum cost path which specifies a sequence of links between nodes and should then be used by the user of the transport network.
Conventionally, for instance, in connection with public bus systems, predetermined fixed schedules or timetables for the buses have been considered.
Additionally, also external parameters influencing the means of transport have been taken into account. For example, U.S. Pat. No. 7,573,866 B2 discloses a method for finding optimum paths using a stochastic network model. The disclosed method aims it finding the shortest paths from a source to destination under some predetermined constraints. An imposed constraint can be a deadline, and further a stochastic influence is included by assuming randomly distributed edge lengths that correspond to costs. The method computes a path that maximizes the probability to arrive before a given deadline.
Known methods for routing in networks present a single shortest path depending on the network topology and time tables, i.e. predetermined routes of means of transport like buses and their fixed arrival and departure times at the bus stops corresponding to nodes. However, in realistic transport systems time tables are often not reliable such that fluctuations between scheduled arrivals and departures may occur. Hence, it is desirable to provide a method for routing taking into account such stochastic fluctuations of the actual transit times between nodes.